package offer;

import java.util.LinkedList;
import java.util.Queue;

public class offerII_0107 {
    public int[][] updateMatrix(int[][] mat) {
        int m= mat.length;
        int n=mat[0].length;
        boolean[][] used=new boolean[m][n];
        Queue<int[]> queue=new LinkedList<>();
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if(mat[i][j]==0){
                    used[i][j]=true;
                    queue.add(new int[]{i,j,0});
                }
            }
        }
        while(!queue.isEmpty()){
            int i=queue.peek()[0];
            int j=queue.peek()[1];
            int k=queue.poll()[2];
            if(range(i-1,j,used)){
                mat[i-1][j]=k+1;
                used[i-1][j]=true;
                queue.add(new int[]{i-1,j,k+1});
            }
            if(range(i+1,j,used)){
                mat[i+1][j]=k+1;
                used[i+1][j]=true;
                queue.add(new int[]{i+1,j,k+1});
            }
            if(range(i,j-1,used)){
                mat[i][j-1]=k+1;
                used[i][j-1]=true;
                queue.add(new int[]{i,j-1,k+1});
            }
            if(range(i,j+1,used)){
                mat[i][j+1]=k+1;
                used[i][j+1]=true;
                queue.add(new int[]{i,j+1,k+1});
            }
        }
        return mat;

    }
    public boolean range(int i,int j,boolean[][] used){
        if(i>=0&&i< used.length&&j>=0&&j<used[0].length&&used[i][j]==false) return true;
        return false;
    }
}
